#pragma once

#include <boost/shared_ptr.hpp>
#include <map>
#include <vector>

namespace SmsAlg {


    /**
     * This class implements a graph data structure. The class is designed for a unidirectional 
     * discharged graph. 
     */
    template <typename NodeDataType, typename LinkDataType>
    class Graph {
    public:

        class Node 
        {
        private:
            /**
             * If the node is invisible then all of the connected nodes and their links are 
             * invisible too. 
             */
            bool _visible; 
        public:
            /**
             * Some data can be associated with the node through this field. 
             */
            NodeDataType _data;
            
            void SetVisible(bool vis)
            {
                _visible = vis;
            }
            bool Visible()
            {
                return _visible;
            }

            Node (NodeDataType data) 
            {
                _data = data;
                _visible = false;
            }
        };
        typedef boost::shared_ptr<Node> NodePtr;

        class Link 
        {
        private:
            /**
             * If the link is invisible then the target node is invisible too. 
             */
            bool _visible; 
        public:
            /**
             * Source node. 
             */
            NodePtr _srcNode;
            /**
             * Destination node. 
             */
            NodePtr _dstNode;
            /**
             * Some data can be associated with the link through this field. 
             */
            LinkDataType _data;

        
            Link (NodePtr srcNode, NodePtr dstNode, LinkDataType linkData)
            {
                _srcNode = srcNode;
                _dstNode = dstNode;
                _data = linkData;
                _visible = false;
            }

            void SetVisible(bool vis)
            {
                _visible = vis;
            }
            bool Visible()
            {
                return _visible;
            }
        };
        typedef boost::shared_ptr<Link> LinkPtr;


    public:
        Graph () 
        {
        }

        LinkPtr AddLink (NodePtr srcNode, NodePtr dstNode, LinkDataType linkData) 
        {
            LinkPtr link (new Link(srcNode, dstNode, linkData));
            links.push_back(link);
            //linksBySrcAndDst[std::pair<NodePtr, NodePtr>(srcNode, dstNode)] = link;

            linksByDst[dstNode].push_back(link);
            return link;
        }

        /**
         * Returns true if there is a path from the source node to the destination node. 
         * Note: Visibility of nodes and links is not considered here. 
         * 
         * \param srcData   The data associated with the source node. 
         * \param dstNode   The data associated with the destination node. 
         */
        bool IsNodesConnected(const NodeDataType & srcData, const NodeDataType & dstData) const
        {
            for (std::map<NodePtr, std::vector<LinkPtr>>::const_iterator it = linksByDst.begin();
                it != linksByDst.end(); it++)
            {
                for (std::vector<LinkPtr>::const_iterator lIt = it->second.begin(); 
                    it->first->_data == dstData && lIt != it->second.end(); lIt++)
                {
                    if ( (*lIt)->_srcNode->_data == srcData)
                    {
                        return true;
                    }
                }
            }
            return false;
        }

        /**
         * Finds a link between two nodes. Returns an empty pointer 
         * if nodes are not connected. 
         */ 
        LinkPtr GetLink(const NodePtr & src, const NodePtr & dst)
        {
            if (linksByDst.find(dst) != linksByDst.end())
            {
                std::vector<LinkPtr> & ls = linksByDst[dst];
                for (int i = 0; i < (int) ls.size(); i++)
                {
                    LinkPtr & l = ls[i];
                    assert( l->_dstNode->_data == dst->_data);
                    assert(dst == l->_dstNode);
                    if (src == l->_srcNode)
                    {
                        assert(src->_data == l->_srcNode->_data);
                        return l;
                    }
                }
            }
            return LinkPtr();
        }

        void RemoveLinks()
        {
            links.clear();
            linksByDst.clear();
        }

        /**
        * Merges two graphs. 
        */
        static Graph<NodeDataType, LinkDataType> Merge (const Graph<NodeDataType, LinkDataType> & g1, 
            const Graph<NodeDataType, LinkDataType> & g2)
        {
            Graph<NodeDataType, LinkDataType> g;
            g.nodes = g1.nodes;
            for (int i = 0; i < (int) g2.nodes.size(); i++)
            {
                if (std::find(g.nodes.begin(), g.nodes.end(), g2.nodes[i]) == g.nodes.end())
                {
                    g.nodes.push_back(g2.nodes[i]);
                }
            }
            g.links = g1.links;
            for (int i = 0; i < (int) g2.links.size(); i++)
            {
                if (std::find(g.links.begin(), g.links.end(), g2.links[i]) == g.links.end())
                {
                    g.links.push_back(g2.links[i]);
                }
            }
            g.linksByDst = g1.linksByDst;
            for (std::map<NodePtr, std::vector<LinkPtr>>::const_iterator it = g2.linksByDst.begin(); 
                it != g2.linksByDst.end(); it++)
            {
                std::vector<LinkPtr> & ls = g.linksByDst[it->first];
                const std::vector<LinkPtr> & ls2 = it->second;
                for(int i = 0; i < (int) ls2.size(); i++)
                {
                    if (std::find(ls.begin(), ls.end(), ls2[i]) == ls.end())
                    {
                        ls.push_back(ls2[i]);
                    }
                }
            }
            return g;
        }

    public:
        std::vector<LinkPtr> links; 
        std::vector<NodePtr> nodes;
        //std::map<std::pair<NodePtr, NodePtr>, LinkPtr> linksBySrcAndDst;
        std::map<NodePtr, std::vector<LinkPtr> > linksByDst; 
    };
} 
